package os;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;

/**
 * @author mubei
 * @date 2021/12/8
 * @description  最近最久未使用
 */
public class LRU {
    final int N = 100;
    HashMap<Integer, Integer> virtualMemory;
    int size;
    int index = 0;
    int arr[] = new int[N];
    int map[][];
    char identifying[] = new char[N];
    int count = 0;

    public LRU(int size) {
        this.size = size;
        map = new int[size][N];
        virtualMemory = new HashMap<Integer, Integer>();
        Arrays.fill(identifying, '×');
        //✓
    }

    public void calc() {
        Scanner scanner = new Scanner(System.in);
        System.out.println("输入若干页面 #号结束");
        while (!scanner.hasNext("#")) {
            if (index > 0) {
                for (int i = 0; i < size; i++) {
                    map[i][index] = map[i][index - 1];
                }
            }
            int page = scanner.nextInt();
            // 判断页面是否已经存在
            arr[index] = page;
            if(virtualMemory.containsKey(page)){
                virtualMemory.put(page,index);
            }else{
                if(virtualMemory.size() < size){
                    addPage(page);
                }else{
                    replacePage(page);
                }
            }
            index++;

        }
        print();
    }

    private void addPage(int page){
        virtualMemory.put(page,index);
        int pointer = -1;
        for (int i = 0; i < size; i++) {
            if(  map[i][index] == 0){
                pointer = i;
                break;
            }
        }
        map[pointer][index] = page;
        identifying[index] = '✓';
        count++;
    }

    private void replacePage(int page){
        int pointer = -1;
        int oldTime = Integer.MAX_VALUE;
        // 找到最久未使用的
        int findKey = -1;
        for (Integer key : virtualMemory.keySet()) {
            if(oldTime > virtualMemory.get(key)){
                // 找到map中哪个位置存放key
                for (int i = 0; i < size; i++) {
                    if(map[i][index-1] == key){
                        pointer = i;
                        findKey = key;
                    }
                }
                oldTime = virtualMemory.get(key);
            }
        }
        virtualMemory.remove(findKey);
        virtualMemory.put(page,index);
        map[pointer][index] = page;
        identifying[index] = '✓';
        count++;

    }

    private void print(){
        for (int i = 0; i < index; i++) {
            System.out.print(arr[i]+"\t");
        }
        System.out.println();
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < index; j++) {
                System.out.print(map[i][j]+"\t");
            }
            System.out.println();
        }
        for (int i = 0; i < index; i++) {
            System.out.print(identifying[i]+"\t");
        }
        System.out.println();
        System.out.println("一共替换 "+count+"次");
    }

}
